1. Field of the Invention
This invention relates generally to computer networks and, more particularly, to a method and apparatus for routing a packet in a computer network.
2. Description of the Related Art
Local area networks (xe2x80x9cLANsxe2x80x9d) are now commonplace. A LAN is a computer network that spans a relatively small area. Most LANs connect workstations and/or personal computers in a way that enables a user to access data and devices at any of the locations on the LAN so that many users can share expensive types of devices such as laser printers and can share information.
There are many types of LANs. Common examples include token ring networks and Ethernets. A token ring network is a type of computer network in which the computers are schematically arranged in a circle. A packet of digital information, called a xe2x80x9ctoken,xe2x80x9d travels around the circle. To send a message, a computer attaches its message to the token and lets the token continue traveling around the network. Each computer checks the message when it receives a token to see if it is the intended destination and, if so, removes the message from the token. An Ethernet is a bus network in which packets of digital information travel up and down the bus. Although these are the most common type of LANs, there are still others, such as ARCnet, in use.
FIG. 1 depicts a prior art computer network 10 that will be used to illustrate several concepts associated with the invention. The computer network 10 generally comprises a first LAN 12, a second LAN 14, and a router 15. A xe2x80x9crouterxe2x80x9d is a device that connects two or more LANs as shown in FIG. 1 and in a manner described more fully below. The first LAN 12 includes a server 16 and two workstations 18. The second LAN 14 similarly includes a second server 20 and two workstations 22. Each of the router 15, the server 16, the workstations 18, the server 20, and the workstations 22 may be generally referred to as a xe2x80x9cLAN device.xe2x80x9d The various components of the computer network 10 are interconnected by communication links 23, 24, and 25, which may be any type of media such as twisted pair wires, coaxial cables, fiber optic cables, or some combination thereof. Some LANs even use wireless communications links, such as radio or infrared waves.
The workstations 18 and workstations 22 can send messages to one another through the network 10 in xe2x80x9cpacketsxe2x80x9d of digital information. Each device on the network 10 is assigned a physical address. Each packet contains a destination address for one of the other workstations and message data. Thus, for one workstation 18 to communicate with the other workstation 18, the first workstation 18 composes a packet which is then electronically transmitted to the other workstation 18 over the LAN 12 through the communications links 24. The workstations 22 use this same process. However, for a workstation 18 to transmit a message to a workstation 22, the workstation 18 must compose a data packet that is transmitted via the router 15.
The manner in which the LAN devices communicate is determined by a xe2x80x9cprotocol.xe2x80x9d A protocol is an agreed upon format for transmitting data between and among devices. Thus, the network""s protocol determines the composition, transmission, receipt, and decomposition of the packets. Most networks use some form of the transport control protocol/Internet protocol (xe2x80x9cTCP/IPxe2x80x9d). The TCP/IP protocol is actually a group of protocols. Note that, although the term xe2x80x9cInternetxe2x80x9d appears in the name of the protocol, its application is not limited to the Internet, other wide area networks (xe2x80x9cWANsxe2x80x9d), or any other type of network.
The TCP/IP protocols are typically used to implement computer networks, such as the computer network 10, dictate that the destination address for any individual packet have at least two parts. One part of the address is very general and one part of the address is very specific. The general part of the address is known as the Internet protocol (xe2x80x9cIPxe2x80x9d) address and determines whether the packet is sent to its destination through the router 15. The router 15 then determines, or xe2x80x9cresolves,xe2x80x9d the specific physical address of the packet""s destination from the IP address carried by the packet. Thus, the IP address is not an actual physical address, but instead merely represents a physical address.
When the router 15 receives a packet, it determines whether it knows the physical address represented by the IP address. The router 15 temporarily stores physical addresses to which it has recently transmitted, and checks this store whenever it receives a packet. If the physical address of the received packet can be determined from the stored information, the router 15 transmits the packet right away. If not, then the router 15 must xe2x80x9cresolvexe2x80x9d the physical address. The router 15 typically does this using what is known as an xe2x80x9caddress resolution protocolxe2x80x9d (xe2x80x9cARPxe2x80x9d).
The ARP is part of the TCP/IP protocol suite and is used to convert an IP address into the physical address that is the destination of the packet. The ARP requires the router 15 to broadcast to all LAN devices on the network 10 what is known as an ARP request. The ARP request instructs the LAN device corresponding to the IP address to respond by transmitting its physical address back to the router 15. The intended destination then replies to the request with its physical hardware address. The router 15 receives the physical address and stores it temporarily.
During the ARP, the router 15 either retains or discards the packet for which the ARP is issued. If the packet is retained, the router 15 simply transmits it to whichever LAN device responded to the ARP request. However, some routers do not retain the packet during ARP and the packet is lost. The LAN devices are typically programmed for this eventuality such that they will send the packet to the router 15 several times. Thus, the router 15 might receive the packet two or three times while transmitting the packet to the destination only on the second or third try.
For example, assume that a workstation 18 transmits a data packet to a workstation 22 over the network 10 and that the router 15 does not retain the data packet. The workstation 18 transmits the data packet over the LAN 12 to the router 15. The router 15 then broadcasts an ARP request and the workstation 22 replies to the request by sending its physical address to the router 15. In the meantime, the router 15 has dropped the data packet. The router 15 then receives the physical address of the workstation 22 over the LAN 14 and temporarily stores it. The workstation 18 once again sends the data packet to the router 15. The router 15 then checks its memory, finds the previously resolved physical address of the workstation 22, and forwards the data packet to the workstation 22. Although such a network obviously lacks something in efficiency, this protocol simplifies the design and reduces the cost of implementing the network 10 overall.
This procedure works reasonably well unless one or more of the LAN devices on the network 10 includes a power management feature that inactivates the LAN device when not in use. If, for instance, a workstation 22 incorporates a power management system, the operating system of the workstation 22 will switch to a xe2x80x9csleepxe2x80x9d state to reduce power consumption after a predetermined period of inactivity. When the router 15 broadcasts an ARP request to which a sleeping workstation 22 should respond, the workstation 22 has to xe2x80x9cwake upxe2x80x9d before responding.
The presence of power-managed devices is important because of the way they typically implement their retention capabilities. LAN devices such as the servers 16 and 20 and the workstations 18 and 22 typically have a retention capability. However, the retention capability for some devices deactivates when the device goes to sleep. Thus, in the context of ARP, the LAN device when it is asleep may retain the ARP request or discard it depending on its retention capabilities. The sleep-state retention capability for LAN devices is expensive to implement and was previously thought to be non-critical. Many computer networks such as the network 10 are therefore implemented with LAN devices omitting a sleep-state retention capability for cost reasons. However, recent information indicates that sleep-state retention capability is extremely critical in some implementations to prevent LAN connection failures and lost information
Assume again the previous scenario, except that (1) the destination workstation 22 is a power-managed device, (2) the workstation 22 lacks a sleep-state retention capability, and (3) the workstation 22 is asleep at the time the data packet is first transmitted. The first ARP request awakens the workstation 22. While the workstation 22 is awakening, the source workstation 18 may re-send one or more data packets with the router 15 broadcasting another ARP request for each data packet, again dropping the data packets. The destination workstation 22 in this scenario cannot respond to the first ARP request upon awakening because it has not been retained. Once the destination workstation 22 is awakened, it can respond to one of the subsequent ARP requests so that the router 15 can resolve its physical address. However, in some circumstances, by the time the physical address of the workstation 22 is finally resolved, the source workstation 18 has quit re-sending the packet. Thus, although the router 15 has now resolved and stored the address and the destination workstation 22 is awake, the connection has failed and the information is lost.
The present invention is directed to overcoming, or at least reducing the effects of, one or more of the problems set forth above.
The invention in one embodiment is a method for routing a packet in a network. The method includes transmitting a first data packet to a destination; provoking resolution of the destination address of the first data packet; and transmitting a second data packet to the destination after the destination address is resolved.